package solution.search;

import junit.framework.Assert;
import lib.util.Mutable;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 */
public class BinarySearch {
	/**
	 * Find a range of numbers
	 * 
	 * @param data
	 *            the array to search
	 * @param rangeStart
	 *            find [pStart .. pEnd] so that rangeStart <= x <= rangeEnd.
	 * @param rangeEnd
	 * @param pStart
	 *            the start and end position of the range
	 * @param pEnd
	 * 
	 *            check: http://www.sureinterview.com/shwqst/545001
	 */
	public void findRange(double[] data, double rangeStart, double rangeEnd,
			Mutable<Integer> pStart, Mutable<Integer> pEnd) {
		pStart.setValue(-1);
		pEnd.setValue(-1);

		if (data == null || data.length == 0)
			return;

		int posStart = 0, posEnd = data.length - 1;

		// find where the data roughly is.
		int inRange = 0;
		while (posStart <= posEnd) {
			inRange = (posStart + posEnd) / 2;
			if (data[inRange] < rangeStart) {
				posStart = inRange + 1;
			} else if (data[inRange] > rangeEnd) {
				posEnd = inRange - 1;
			} else {
				// found: rangeStart <= data[inRange] <= rangeEnd;
				break;
			}
		}
		// not found
		if (posStart > posEnd)
			return;

		// Now, data[inRange] is in the range of data.
		// We need to find the index that points to rangeStart.
		int pEnd2 = inRange;
		while (posStart <= pEnd2) {
			int n = (posStart + pEnd2) / 2;
			if (data[n] < rangeStart) {
				posStart = n + 1;
			} else {
				pEnd2 = n - 1;
			}
			// note: there is no break when rangeStart was found.
		}

		// and find the end position in [inRange,posEnd]
		int pStart2 = inRange;
		while (pStart2 <= posEnd) {
			int n = (pStart2 + posEnd) / 2;
			if (data[n] > rangeEnd) {
				posEnd = n - 1;
			} else {
				pStart2 = n + 1;
			}
			// note: there is no break;
		}

		if (posStart <= posEnd) {
			pStart.setValue(posStart);
			pEnd.setValue(posEnd);
		}
	}

	@Test
	public void testRange() {
		double[][][] data = new double[][][] {//
		//
				{ { 0.1, 0.1, 0.1, 0.2, 0.3 }, { 0, 3 } }, //
				{ { 0.1, 0.1, 0.1, 0.1, 0.2, 0.3 }, { 0, 4 } }, //
				{ { 0.0, 0.1, 0.1, 0.1, 0.2, 0.3 }, { 1, 4 } }, //
				{ { 0.0, 0.0, 0.1, 0.1, 0.1, 0.2, 0.2, 0.2, 0.3 }, { 2, 7 } }, //
				{ { 0.0, 0.0, 0.1, 0.1, 0.1, 0.2, 0.2, 0.2 }, { 2, 7 } }, //
				{ { 0.0, 0.0, 0.1, 0.1, 0.1 }, { 2, 4 } }, //
				{ { 0.0, 0.0, 0.2, 0.2, 0.2 }, { 2, 4 } }, //
				{ { 0.2, 0.2, 0.2 }, { 0, 2 } }, //
				{ { 0.3, 0.3 }, { -1, -1 } }, //
				{ { 0.0, 0.3 }, { -1, -1 } }, //
		};

		for (double[][] element : data) {
			Mutable<Integer> ms = new Mutable<Integer>();
			Mutable<Integer> me = new Mutable<Integer>();
			findRange(element[0], 0.1, 0.2, ms, me);
			System.out.println(ms.getValue() + "," + me.getValue());
			Assert.assertEquals(element[1][0], ms.getValue(), 0.01);
			Assert.assertEquals(element[1][1], me.getValue(), 0.01);
		}
	}
}
